// Copyright (c) 2009 Johnathan Traugott & Christopher Keith (chris.keith@gmail.com)
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following
// conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.

// Sort comparisons. Also a mergeSort using only one extra buffer.

#include <iostream>
#include <algorithm>
#include <vector>
#include <exception>
#include <cmath>
using namespace std;

#include "windows.h"

class RecursiveMergeSorter {
public:
          RecursiveMergeSorter(int *array, int length, bool trace = false);
  virtual int    *Sort();
protected:
  void    Merge(int *tgt, int *src1, int src1Length, int *src2, int src2Length);
  int    *mArray;
  int     mLength;
private:
  int    *SortHelper(int *a, int length);
};

class IterativeMergeSorter : public RecursiveMergeSorter {
public:
  IterativeMergeSorter(int *array, int length, bool trace = false) :
      RecursiveMergeSorter(array, length, trace) {}
  int    *Sort();
};

class SortTester {
public:
  void          RunTests(int sortType);
  static void   PrintArray(char* msg, int *array, int length);
private:
  void          STLSort(int nums[], int length, bool useArray);
};

RecursiveMergeSorter::RecursiveMergeSorter(int *array, int length, bool trace)
: mArray(array),
  mLength(length)
{
}

int *RecursiveMergeSorter::Sort() {
  return SortHelper(mArray, mLength);
}

void RecursiveMergeSorter::Merge(int *tgt, int *src1, int src1Length, int *src2, int src2Length) {
  int i1 = 0;
  int i2 = 0;
  int tgtIndex = 0;
  while ( (i1 < src1Length)  && (i2 < src2Length) ) {
    if (src1[ i1 ] < src2[ i2 ]) {
      tgt[ tgtIndex++ ] = src1[ i1++ ];
    } else {
      tgt[ tgtIndex++ ] = src2[ i2++ ];
    }
  }
  while (i1 < src1Length) {
    tgt[ tgtIndex++ ] = src1[ i1++ ];
  }
  while (i2 < src2Length) {
    tgt[ tgtIndex++ ] = src2[ i2++ ];
  }
}

int* RecursiveMergeSorter::SortHelper(int *a, int length) {
  if (length == 0) {
    cout << "RecursiveMergeSorter::SortHelper(int *a, int length): length must be > 0" << endl;
    return NULL;
  }
  int  *b = new int[length];
  if (length == 1) {
    b[0] = a[0];
  } else {
    int   len1 = length / 2;
    int   len2 = length - len1;
    int  *b1 = SortHelper(a, len1);
    int  *b2 = SortHelper(&a[len1], len2);
    Merge(b, b1, len1, b2, len2);
    delete[] b1;
    delete[] b2;
  }
  return b;
}

int *IterativeMergeSorter::Sort() {
  int*  src = mArray;
  int*  tgt = new int[mLength];
  for (int swapSize = 1; swapSize < mLength; swapSize *= 2) {
    for (int j = 0; j < mLength; j += (2 * swapSize)) {
      int start = j;
      int sizeOfSrc1 = min(swapSize, mLength - start);
      int src2Index = start + swapSize;
      int remainder = max(0, mLength - src2Index);
      int sizeofSrc2 = min(swapSize, remainder);
      Merge(&tgt[start], &src[start], sizeOfSrc1,
                         &src[src2Index], sizeofSrc2);
    }
    int*  temp = src;
    src = tgt;
    tgt = temp;
  }
  if (src != mArray) {
    memcpy(mArray, src, mLength * sizeof(int));
    tgt = src;
  }
  delete[] tgt;
  return mArray;
}



void insertionSort(int  nums[], int len) {
  int   first;
  int   location;
  for (first = 1; first < len; first++) {
    if (nums[first] < nums[first - 1]) {
      int   temp = nums[first];
      location = first;
      do {
        nums[location] = nums[location - 1];
        location--;
      } while ((location > 0)&& (nums[location - 1] > temp));
      nums[location] = temp;
    }
  }
}
void mergeSort1(int  nums[], int len) {
    RecursiveMergeSorter m(nums, len, false);
    m.Sort();
}

void mergeSort2(int  nums[], int len) {
    IterativeMergeSorter m(nums, len, false);
    m.Sort();
}

void heapify(int* list, int low, int high) {
  int temp = list[low];
  int largeIndex = 2 * low + 1;
  while (largeIndex <= high) {
    if (largeIndex < high) {
      if (list[largeIndex] < list[largeIndex + 1]) {
        largeIndex++;
      }
    }
    if (temp > list[largeIndex]) {
      break;
    }
    list[low] = list[largeIndex];
    low = largeIndex;
    largeIndex = 2 * low + 1;
  }
  list[low] = temp;
}

void buildHeap(int* list, int length) {
  for (int index = length / 2 - 1; index >= 0; index--) {
    heapify(list, index, length - 1);
  }
}

void heapSort(int  list[], int length) {
  buildHeap(list, length);
  for (int lastOutOfOrder = length - 1; lastOutOfOrder >= 0; lastOutOfOrder--) {
    int temp = list[lastOutOfOrder];
    list[lastOutOfOrder] = list[0];
    list[0] = temp;
    heapify(list, 0, lastOutOfOrder - 1);
  }
}

int compareInts(const void* a, const void* b) {
  return *((int*)a) - *((int*)b);
}

void systemQSort(int nums[], int length) {
  qsort(nums, length, sizeof(int), compareInts);
}

void stlSortVector(int nums[], int length) {
  vector<int> myvector (nums, nums + length);
  // using default comparison (operator <):
  long  start = GetTickCount();
  sort (myvector.begin(), myvector.begin() + length);
	cout << (GetTickCount() - start) << "\t";
}

void stlSortArray(int nums[], int length) {
  long  start = GetTickCount();
  sort( nums, &nums[length]);
	cout << (GetTickCount() - start) << "\t";
}

void SortTester::STLSort(int nums[], int length, bool useArray) {
  if (useArray) {
    sort(nums, &nums[length]);
  } else {
  vector<int> myvector (nums, nums + length);
  sort (myvector.begin(), myvector.begin() + length);
  int i = 0;
  vector<int>::iterator it;
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    nums[i++] = *it;
  }
}

void SortTester::PrintArray(char* msg, int *array, int length) {
  cout << msg << " { ";
  for (int i = 0 ; i < length; i++) {
    if (i > 0) {
      cout << ", ";
    }
    cout << array[i];
  }
  cout << " }" << endl;
}

void SortTester::RunTests(int sortType) {
  for (int i = 1; i < 10; i++) {
    int   *array = new int[i];
    for (int j = 0; j < i; j++) {
      array[j] = i - j;
    }
    int *result;
    switch (sortType) {
      case 1 : {
        RecursiveMergeSorter m(array, i, true);
        result = m.Sort();
        PrintArray("RecursiveMergeSorter", result, i);
        delete[] result;
        break;
       }
      case 2 : {
        IterativeMergeSorter m(array, i, true);
        result = m.Sort();
        PrintArray("IterativeMergeSorter", result, i);
        break;
      }
      case 3 : {
        heapSort(array, i);
        PrintArray("heapSort", array, i);
        break;
      }
      case 4 : {
        STLSort(array, i, true);
        PrintArray("STL Sort array ", array, i);
        break;
      }
      case 5 : {
        STLSort(array, i, false);
        PrintArray("STL Sort vector", array, i);
        break;
      }
      default : {
        cout << "Unknown sort type: " << sortType << endl;
        break;
      }
    }
    delete[] array;
  }
}

void testSort() {
  SortTester m;
  for (int i = 1; i < 6; i++) {
    m.RunTests(i);
  }
  char ch;
  cin.get(ch);
}

/*
	CSCI 20
	Jon Traugott
	March 19 2008
	Determine the runtimes for various sorting functions.
*/
	
const int MAXSIZE = 40000000;
int buf1[MAXSIZE],  // to hold the orig. list of random numbers
	buf2[MAXSIZE];  // to hold a copy of the numbers for sorting
	

void sort0(int  nums[], int len);
void sort1(int  nums[], int len);
void sort2(int  nums[], int len);
void sort3(int  nums[], int len);
void sort4(int  nums[], int len);
void IterativeQuickSort(int  nums[], int len);
int  partition(int   nums[], int val , int len);	
void print(int  nums[], int len);
void fill(int   nums[], int len, char orderCode) ;
void copyTo(int from[], int to[], int len) ;

unsigned long timeIt(void (*sort)(int [], int),int  nums[], int len) {
  long  start = GetTickCount();
	sort(nums,len);
	return (GetTickCount() - start);  // elapsed time
}

void (*sorts[]) (int[],int) =
                { sort4,         IterativeQuickSort,  mergeSort2,     systemQSort, stlSortArray,     heapSort };
char* names[] = {"quick(recu)", "quick(iter)",       "merge(2-buf)", "'c' qsort", "STL sort array", "heap" };

void runSort(const char* name, int size, char fillType, int i) {
  if ((strcmp(name, "quick") == 0) && (fillType != 'r')) {
	cout << "gives stack overflow...";
  } else {
	for (int nRuns = 0; nRuns < 1; nRuns++) {
	  fill(buf1, size, fillType);  // store a list of random numbers
	  copyTo(buf1, buf2, size);
	  if (strcmp(name, "STL sort array") == 0) {
		stlSortArray(buf2, size);
	  } else if (strcmp(name, "STL sort vector") == 0) {
		stlSortVector(buf2, size);
	  } else {
		cout << timeIt(*sorts[i], buf2, size) << "\t";
	  }
	}
  }
}
int startSize =  2000000;
int endSize   = 20000000;
int incSize   =  2000000;
void runTests(char* title, char fillType) {
  try {
		cout << "\t\t";
	  for (int t = startSize; t <= endSize; t += incSize) {
      cout << t << "\t";
    }
		cout << endl;
	  int numSorts = sizeof(names) / sizeof(char *);
	  for (int i = 0; i < numSorts; i++) {
			cout << title << "\t" << names[i] << "\t";
		  for (int size = startSize; size <= endSize; size += incSize) {
			  runSort(names[i], size, fillType, i);
		  }
			cout << endl;
    }
  }
  catch (exception& e) {
    cout << e.what() << endl;
  }
}

int main() {
 // testSort(); return 0; // to make sure that sorts work correctly.
	cout << "Starting..." << endl;
  runTests("Random numbers:", 'r');
  // runTests("Ascending numbers:", 'a');
  // runTests("Descending numbers:", 'd');
  cout << "Done!" << endl;
  char c;
  cin.get(c);
  return 0;
}

void sort0(int  nums[], int len) {
	if (len <= 1) return;
	sort0(nums+1, len-1);
	if (nums[0] > nums[1]) 
		swap(nums[0],nums[1]);
	sort0(nums+1,len-1);
}	   


void sort1(int  nums[], int len) {
	if (len <= 1) return;
	sort1(nums+1, len-1);
	if (nums[0] > nums[1])  {
		swap(nums[0],nums[1]);
		sort1(nums+1,len-1);
	}
}

void sort2(int  nums[], int len) {
	for (int i = len-1; i > 0; i--)
		for (int j = 0; j < i; j++) 
			if (nums[j] > nums[j+1]) 
				swap(nums[j], nums[j+1]);
}

void sort3(int  nums[], int len) {
	for (int start = 0; start < len; start++) {
		int minIndex = start;
		for (int i = start+1; i < len; i++) 
			if (nums[minIndex] > nums[i])
				minIndex = i;
		swap(nums[start], nums[minIndex]);
	}
}


// Move all elements less than val to the left side of the array. 
// Return index of the first element greater than val.
int partition(int  a[], int val , int len) {
  int marker = 0;
  for (int i = 1; i < len; i++)
	  if (a[i] < val) {
		  swap(a[marker], a[i]);
		  marker++;
	  }
  return marker;
}

void sort4(int  nums[], int len) {
	if (len < 2) return;
	int mid = partition(nums, nums[0], len);
	if (mid == 0) mid++; // nums[0] was the smallest
	sort4(nums, mid);
	sort4(nums + mid, len - mid);
}
/// Sort the array between a low and high bound in either ascending or descending order
/// Parameters: 
///      int  nFirst : between 0 and the upper bound of the array.
///      int  nLast  : between 0 and the upper bound of the array.
///                  : must be guaranteed >= nFirst.
///      bool bAscend: true  - sort in ascending order
///                  : false - sort in descending order
void IterativeQuickSort(int nData[], int nLast)
{
    nLast--; // length is passed in...
    int nFirst = 0;
    bool bAscend = true;
    bool bSortOK = false;

    int i, j, nStkPtr = 0, nTmp;
    bool bSortCompleted = false, bDirection = true;

    // get the maximum size of stack required:
    int nStackMax = (int)((log((float)nLast) + 3) * 2); // from Knuth Vol 3.
    // Note, +3 is added because: 
    // +1 to round up rather than down, 
    // +1 because it's a full bottom-up stack (ie Stack[0] is never used),
    // +1 because data array is zero-indexed.

    int** nStack = new int*[nStackMax];
    for (int k = 0; k < nStackMax; k++) {
      nStack[k] = new int[2];
    }

    do
    {
        do
        {
            i = nFirst;
            j = nLast;
            bDirection = true;

            do
            {
                if ((nData[i] > nData[j]) == bAscend)
                {
                    // Swap the two items in the list pointed to by i and j
                    nTmp = nData[i];
                    nData[i] = nData[j];
                    nData[j] = nTmp;
                    bDirection = !bDirection;
                }

                if (bDirection)
                    j--;
                else
                    i++;

            }
            while (i < j);

            if (i + 1 < nLast)
            {
                // There's another partition to be sorted
                nStkPtr++;
                nStack[nStkPtr][0] = i + 1;
                nStack[nStkPtr][1] = nLast;
            }
            nLast = i - 1;

        }
        while (nFirst < nLast);

        if (nStkPtr == 0)
        {
            // No more partitions to sort, so by definition we've finished!
            bSortCompleted = true;
        }

        else
        {
            // Pop the most recently stored partition and sort that
            nFirst = nStack[nStkPtr][0];
            nLast = nStack[nStkPtr][1];
            nStkPtr--;
        }
    }

    while (!bSortCompleted);
}

void print(int nums[], int len) {
	for (int i = 0; i< len; i++)
		cout << nums[i] << " ";
	cout << endl << endl;
}

void fill(int nums[], int len, char orderCode) {
	for (int i = 0; i < len; i++) {
		if (orderCode == 'a') nums[i] = i+1;
		else if (orderCode == 'd') nums[i] = len - i;
		else {
			int n = 0;
			for (int j = 0; j < rand()%50+1; j++) {
				int k = rand()%100 * (rand()+1);
				n += (rand()%2 == 0 ? k : -k); // a random walk
			}
			nums[i] = n;
		}  
	}
}

int random10(int powOf10) {
	int num = 0;
	if (powOf10 > 9) {
		cout << "Limit is 10^9" << endl;
		powOf10 = 9;
	}
	while (powOf10-- > 0)
		num = num * 10 + rand() % 10;
	return num;
}

void fill2(int nums[], int len, char orderCode) {
	int digits = int(log(len*1.0)/log(10.0) +0.5);
	cout << "digits = " << digits << endl;
	for (int i = 0; i < len; i++) {
		if (orderCode == 'a') nums[i] = i+1;
		else if (orderCode == 'd') nums[i] = len - i;
		else {
			
			nums[i] = random10(digits + 1);
		}  
	}
}
void copyTo(int from[], int to[], int len) {
	for (int i = 0; i < len ;i++)
		to[i] = from [i];
}


